// 《围棋》作者版权所有。保留所有权利。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

package runtime

import (
	"internal/cpu"
	"internal/goarch"
	"runtime/internal/atomic"
	"unsafe"
)

// spanSet是一组*mspan。
// 
// spanSet对于并发推送和弹出操作是安全的。
type spanSet struct {
	// spanSet是一种两级数据结构，由一个指向固定大小块的可扩展脊椎组成。脊椎
	// 无需锁即可访问，但添加块或
	// 需要使用脊椎锁。
	// 
	// 因为每个mspan至少覆盖8K堆，并且占用
	// 跨度集中最多8个字节，所以脊椎的增长非常有限。
	// 
	// 脊椎和所有块都是在堆外分配的，这使得
	// 可以在内存管理器中使用，并且避免了
	// 在所有这些块上都需要写屏障。SpanSetBlock是在池中管理的
	// 但从未释放回运行的
	// 系统。我们从不释放spine内存，因为可能存在
	// 并发无锁访问，而且我们可能会重用它
	// 无论如何。（原则上，我们可以在STW期间这样做。）

	spineLock mutex
	spine     unsafe.Pointer // /*[N]*跨距块，按原子方式访问
	spineLen  uintptr        // 脊椎数组长度，按原子方式访问
	spineCap  uintptr        // 脊椎数组帽，按锁方式访问

	// 索引是单个字段中跨距集的头和尾。
	// 头和尾都表示逻辑块的索引
	// 所有块的串联，头始终在后面或
	// 等于尾（表示一个空集）。此字段为
	// 始终以原子方式访问。
	// 
	// 头部和尾部只有32位宽，这意味着我们
	// 在重置前最多只能支持2^32次推送。如果堆中的每个
	// span都存储在这个集合中，并且每个span都是最小的大小（1个运行时页面，8kib），那么不可表示的最小堆大约是32tib。
	index headTailIndex
}

const (
	spanSetBlockEntries = 512 // 64位
	spanSetInitSpineCap = 256 // 足以在64位
)

type spanSetBlock struct {
	// 上实现1GB堆的可用跨距通过无锁堆栈管理锁。
	lfnode

	// popped是在
	// 此块上发生的pop操作数。该数字用于帮助确定
	// /块何时可以安全回收。
	popped uint32

	// spans是此块中的一组跨距。
	spans [spanSetBlockEntries]*mspan
}

// push将span s添加到缓冲区b。push可以安全地与其他push和pop操作同时调用
// 。获得我们的位置。
func (b *spanSet) push(s *mspan) {
	cursor := uintptr(b.index.incTail().tail() - 1)
	top, bottom := cursor/spanSetBlockEntries, cursor%spanSetBlockEntries

	// 我们需要添加块吗？
	spineLen := atomic.Loaduintptr(&b.spineLen)
	var block *spanSetBlock
retry:
	if top < spineLen {
		spine := atomic.Loadp(unsafe.Pointer(&b.spine))
		blockp := add(spine, goarch.PtrSize*top)
		block = (*spanSetBlock)(atomic.Loadp(blockp))
	} else {
		// 在脊椎上添加一个新的块，可能会在脊椎上生长。
		lock(&b.spineLock)
		// 在我们释放锁之前，spineLen无法更改，
		// 但可能在我们等待时更改了。
		spineLen = atomic.Loaduintptr(&b.spineLen)
		if top < spineLen {
			unlock(&b.spineLock)
			goto retry
		}

		if spineLen == b.spineCap {
			// 长出脊柱。
			newCap := b.spineCap * 2
			if newCap == 0 {
				newCap = spanSetInitSpineCap
			}
			newSpine := persistentalloc(newCap*goarch.PtrSize, cpu.CacheLineSize, &memstats.gcMiscSys)
			if b.spineCap != 0 {
				// 块在堆外分配，所以
				// 没有写障碍。
				memmove(newSpine, b.spine, b.spineCap*goarch.PtrSize)
			}
			// Spine是在堆外分配的，因此没有写障碍。
			atomic.StorepNoWB(unsafe.Pointer(&b.spine), newSpine)
			b.spineCap = newCap
			// 我们无法立即释放旧脊椎
			// 因为同时推送较低的索引
			// 可能仍在读取。我们让它泄漏，因为即使是1TB的堆也会在旧的脊椎上浪费不到2MB的内存。如果
			// 这是一个问题，我们可以在STW期间释放旧脊椎。
		}

		// 从池中分配一个新块。
		block = spanSetBlockPool.alloc()

		// 将其添加到脊椎。
		blockp := add(b.spine, goarch.PtrSize*top)
		// 块在堆外分配，因此没有写障碍。我们有一个街区。原子地插入span，因为可能有
		atomic.StorepNoWB(blockp, unsafe.Pointer(block))
		atomic.Storeuintptr(&b.spineLen, spineLen+1)
		unlock(&b.spineLock)
	}

	// 通过块API的并发读卡器。
	atomic.StorepNoWB(unsafe.Pointer(&block.spans[bottom]), unsafe.Pointer(s))
}

// pop从缓冲区b中删除并返回一个span，如果b为空，则返回nil。
// pop可以安全地与其他pop和push操作同时调用。
func (b *spanSet) pop() *mspan {
	var head, tail uint32
claimLoop:
	for {
		headtail := b.index.load()
		head, tail = headtail.split()
		if head >= tail {
			// 据我们所知，buf是空的。
			return nil
		}
		// 检查我们想要声明的头部位置是否真的是
		// 后面有一个区块。
		spineLen := atomic.Loaduintptr(&b.spineLen)
		if spineLen <= uintptr(head)/spanSetBlockEntries {
			// 我们正在进行脊椎生长和分配
			// 一个新的块（可能还有一个新的脊椎！），并试图获取
			// 当前正在推进的索引的跨度。
			// 与其旋转，不如通知打电话的人，
			// 这里目前什么都没有。这是
			// 几乎肯定不值得。
			return nil
		}
		// 尝试通过在更新的压头中套入套管来声明当前压头。
		// 这可能会由于一个推力而暂时失败，该推力会修改
		// 尾部，所以在头部不变的情况下继续尝试。
		want := head
		for want == head {
			if b.index.cas(headtail, makeHeadTailIndex(want+1, tail)) {
				break claimLoop
			}
			headtail = b.index.load()
			head, tail = headtail.split()
		}
		// 我们没能认领我们要找的位置，头也变了，
		// 意思是一个波普尔在我们前面。请从顶部重试，因为
		// buf可能不是空的。
	}
	top, bottom := head/spanSetBlockEntries, head%spanSetBlockEntries

	// 我们可能正在读取一个陈旧的脊椎指针，但由于长度
	// 单调增长，并且我们已经验证了它，我们肯定会从有效块读取
	// 。
	spine := atomic.Loadp(unsafe.Pointer(&b.spine))
	blockp := add(spine, goarch.PtrSize*uintptr(top))

	// 假设脊椎长度是正确的，我们知道我们永远不会在这里看到零块，因为长度总是在
	// 块设置后更新。
	block := (*spanSetBlock)(atomic.Loadp(blockp))
	s := (*mspan)(atomic.Loadp(unsafe.Pointer(&block.spans[bottom])))
	for s == nil {
		// 我们在实际设置的跨距下比赛，但是考虑到我们
		// 知道这个跨距存在一个障碍，这里的比赛窗口是
		// 非常小。再试一次。
		s = (*mspan)(atomic.Loadp(unsafe.Pointer(&block.spans[bottom])))
	}
	// 清除指针。这并不是绝对必要的，但在防御上避免了意外重复使用可能导致内存损坏的块。这样，我们将获得一个零指针访问。
	atomic.StorepNoWB(unsafe.Pointer(&block.spans[bottom]), nil)

	// 增加弹出计数。如果我们是区块中最后一个可能的提升者
	// 请注意，由于种族原因，底部不需要等于spanSetBlockEntries-1 
	// 那么我们有责任释放区块。
	// 
	// 如果我们将popped递增到spanSetBlockEntries，我们可以确定
	// 我们是这个块的最后一个popper，因此释放它是安全的。
	// 当我们到达这里的时候，其他所有的popper一定已经越过了这个障碍（从而完成了
	// 弹出了相应的mspan）。因为
	// 我们是最后一个popper，我们也不必担心并发的
	// 推送器（不可能有）。请注意，我们可能不是占了区块最后一个插槽的popper 
	// 我们只是最后一个完成弹出的
	// 人。
	if atomic.Xadd(&block.popped, 1) == spanSetBlockEntries {
		// 清除块的指针。
		atomic.StorepNoWB(blockp, nil)

		// 将块返回到块池。
		spanSetBlockPool.free(block)
	}
	return s
}

// 重置重置为空的跨距集。它还将清理
// 任何剩余的区块。
// 
// 如果buf不是空的，则抛出。
// 
// reset不能与span集合上的任何其他操作
// 同时调用。
func (b *spanSet) reset() {
	head, tail := b.index.load().split()
	if head < tail {
		print("head = ", head, ", tail = ", tail, "\n")
		throw("attempt to clear non-empty span set")
	}
	top := head / spanSetBlockEntries
	if uintptr(top) < b.spineLen {
		// 如果头部赶上尾部，而集合是空的，
		// 我们可能不会清理包含头部和尾部的块
		// 因为它可能会被再次推入。为了避免由于我们要重置头部和尾部而导致内存泄漏，请立即清除这样一个块（如果存在）。
		blockp := (**spanSetBlock)(add(b.spine, goarch.PtrSize*uintptr(top)))
		block := *blockp
		if block != nil {
			// 检查弹出的值是否正常。
			if block.popped == 0 {
				// popped永远不应该为零，因为这意味着我们至少推送了一个值，但如果此
				// 块指针不是零，则尚未弹出。
				throw("span set block with unpopped elements found in reset")
			}
			if block.popped == spanSetBlockEntries {
				// popped也不应等于spanSetBlockEntries 
				// 因为最后一个popper应该使此插槽中的块指针
				// 为零。
				throw("fully empty unfreed span set block found in reset")
			}

			// 清除指向该块的指针。
			atomic.StorepNoWB(unsafe.Pointer(blockp), nil)

			// 将块返回到块池。
			spanSetBlockPool.free(block)
		}
	}
	b.index.reset()
	atomic.Storeuintptr(&b.spineLen, 0)
}

// spanSetBlockPool是一个全球性的spanSetBlocks池。
var spanSetBlockPool spanSetBlockAlloc

// spanSetBlockAlloc表示一个并发的SpanSetBlock池。
type spanSetBlockAlloc struct {
	stack lfstack
}

// alloc尝试从池中获取一个spanSetBlock，如果失败，则返回一个新的。
func (p *spanSetBlockAlloc) alloc() *spanSetBlock {
	if s := (*spanSetBlock)(p.stack.pop()); s != nil {
		return s
	}
	return (*spanSetBlock)(persistentalloc(unsafe.Sizeof(spanSetBlock{}), cpu.CacheLineSize, &memstats.gcMiscSys))
}

// free将SpanseBlock返回池中。
func (p *spanSetBlockAlloc) free(block *spanSetBlock) {
	atomic.Store(&block.popped, 0)
	p.stack.push(&block.lfnode)
}

// haidTailIndex表示一个队列的32位头和32位尾组合成一个64位值。
type headTailIndex uint64

// makeHeadTailIndex从单独的
// head and tail创建headTailIndex值。
func makeHeadTailIndex(head, tail uint32) headTailIndex {
	return headTailIndex(uint64(head)<<32 | uint64(tail))
}

// head返回headTailIndex值的head。
func (h headTailIndex) head() uint32 {
	return uint32(h >> 32)
}

// tail返回headTailIndex值的尾部。
func (h headTailIndex) tail() uint32 {
	return uint32(h)
}

// 拆分将headTailIndex值拆分为若干部分。
func (h headTailIndex) split() (head uint32, tail uint32) {
	return h.head(), h.tail()
}

// 以原子方式加载读取headTailIndex值。
func (h *headTailIndex) load() headTailIndex {
	return headTailIndex(atomic.Load64((*uint64)(h)))
}

// cas以原子方式比较并交换headTailIndex值。
func (h *headTailIndex) cas(old, new headTailIndex) bool {
	return atomic.Cas64((*uint64)(h), uint64(old), uint64(new))
}

// incHead以原子方式增加headTailIndex的head。
func (h *headTailIndex) incHead() headTailIndex {
	return headTailIndex(atomic.Xadd64((*uint64)(h), (1 << 32)))
}

// decHead原子性地减少headTailIndex的head。
func (h *headTailIndex) decHead() headTailIndex {
	return headTailIndex(atomic.Xadd64((*uint64)(h), -(1 << 32)))
}

// incTail以原子方式递增headTailIndex的尾部。
func (h *headTailIndex) incTail() headTailIndex {
	ht := headTailIndex(atomic.Xadd64((*uint64)(h), +1))
	// 检查溢出。
	if ht.tail() == 0 {
		print("runtime: head = ", ht.head(), ", tail = ", ht.tail(), "\n")
		throw("headTailIndex overflow")
	}
	return ht
}

// 重置将headTailIndex清除为（0,0）。
func (h *headTailIndex) reset() {
	atomic.Store64((*uint64)(h), 0)
}
